1. Technical Field of the Invention
This invention relates to a picture processing device which is used in control ling unmanned running vehicles or recognizing motions of objects to be observed in real time.
2. Related Background Art
In controlling an unmanned movable robot Or an automatic movable vehicle, for example, the pictures of the lines marking of f a lane, and those of the center line and the shoulder lines of a road have to be taken by a camera to be subjected to picture processing. FIG. 1 is a view explaining recognition of a road by means of a picture. FIG. 1(a) shows a picture of a road taken by a camera. FIG. 1(b) is a view in which the picture elements in FIG. 1 (a) having higher brightness (or higher brightness change ratios ) are shown in black points.
As shown in FIG. 1(a), in a camera picture 1 a road 3 is extended at infinity toward a horizontal line 2. Shoulder lines 4 are on both sides of the road 3. A center line 5 is at the center or the road 5. The shoulder lines 4 and the center line 5 of the road 3 have higher brightnesses than the other parts of the road 3 and are shown in continuous dots 4', 5' as shown in FIG. 1(b). Based on this camera picture 1, in order to recognize the direction and curves of the road 3, approximate straight lines L.sub.1, L.sub.2, L.sub.3 interconnecting the dots 4'in FIG. 1(b) are recognized.
As a method for giving the approximate straight lines L, the method called Hough transformation is conventionally known (e.g., Specification of U.S. Pat. No. 3,069,654). This method is explained with reference to FIGS. 24. Assuming that a point P (x.sub.p,y.sub.p) to be processed is present on an original picture depicted by the x y coordinate system as shown in FIG. 2(a), an infinite number of straight lines 1 (i.sub.a, i.sub.b . . . ) can be depicted. Straight lines passing the origin 0 (0,0) and orthogonal to the respective straight lines 1.sub.a, 1.sub.b, . . . can be also depicted. When a length of the straight lines 1 passing the origin 0 (0,0) to the straight lines 1 (1.sub.a, 1.sub.b, . . .) is represented by .rho., and an angle these straight lines form to the x axis is represented by .theta. (.theta..sub.a, .theta..sub.b, . . .), the .rho. and .theta. of the straight lines passing the origin 0 (0,0) are given in the sine curve of FIG. 2( b), i.e., the Hough curve. The length .rho..sub.max between the origin O (O,O) and the point to be processed P (x.sub.p,y.sub.p) is the longest of the straight lines passing the point to be processed P (x.sub.p,y.sub.p). The length is given by EQU .rho..sub.max =(x.sub.p.sup.2 +y.sub.p.sup.2).sup.1/2
and when .theta.=0, .rho..sub.0 =x.sub.p.
Next, as shown in FIG. 3(a), Hough transform of FIG. 2 will be applied to Three points P.sub.1 .about.P.sub.3 a straight line L. The sine curve (Hough curve) in the dot line in FIG. 3(b) is given with respect To the point P.sub.1. The sine curve with respect to the point P.sub.2 is in the one dot line in FIG. 3(b), and that with respect to the point P.sub.3 is in the two dot line in FIG. 3(b). The peaks (.rho..sub.1,.theta..sub.1), (.rho..sub.2,.theta..sub.2) and (.rho..sub.3,.theta..sub.3) of the respective sine curves of FIG. 3(b) correspond to the lengths .rho..sub.1, .rho..sub.1, .rho..sub.3 between the origin 0 (0,0) and the respective points P.sub.1, P.sub.2 and P.sub.3 in FIG. 3(a), and the angles .theta..sub.1, .theta..sub.2, .theta..sub.3 the respective straight lines passing the origin 0 form to the x axis.
In FIG. 3(b), the point of intersection of the three Hough curves (sine curves) has coordinates (.theta..sub.t,.theta..sub.t) which are equal to .rho..sub.t,.theta..sub.t of a straight line passing the origin 0 (0,0) and orthogonal to the straight line L. Thus yb obtaining a point of intersection of such sine curves, an approximate straight line of the curves interconnecting the dots (dark points) in the x-y rectangular coordinate system of an original picture can be obtained (in FIG. 3, however, the curves and the approximate straight line are in agreement).
This will be explained with reference to FIG. 4. It is assumed that a number of dots (points to be processed) to be Hough transformed are on a curve in the x-y coordinate plane (original picture plane) in FIG. 4(a). In FIG. 4(a) three approximate straight lines L.sub.1,L.sub.2,L.sub.3 interconnecting the dots can be depicted. When all the dots are subjected to Hough transform as in FIG. 2, three points of intersections of the sine curves are obtained. The three points of intersection have coordinates (.rho..sub.t1,.theta..sub.t1), (.rho..sub.t2,.theta..sub.t2), (.rho..sub.t3,.theta..sub.t3) in FIG. 4(a). When the occurrence of the point of intersection H is expressed by a .rho.,.theta.,H coordinate system, FIG. 4(b) is given. Accordingly, the approximate straight lines L.sub.1 .about.L.sub.3 of FIG. 1(b) corresponding to the shoulder lines 4 of the road 3 can be given in values of .rho. and .theta. at a peak of H (the occurrence of the point of intersection).
But it is not easy to apply the above described given, based on coordinates (x.sub.p, y.sub.p)) of the point P to be Hough transformation to high speed picture processing in real time. That is, when a Hough curve (sine curve) is given, based on coordinates (x.sub.p,y.sub.p) of the point P to be processed on the original picture of FIG. 2 as data, EQU .rho.=x.sub.p .multidot.sin.theta.+y.sub.p .multidot.cos.theta.(1)
must be satisfied. For example, when .rho. is divided into 512 sections, the trigonometric function calculation has to be performed 1024 times: the multiplication, 1024 times; and the addition, 512 times. Besides, when the original picture to be subjected to the computation comprises 512.times.512 picture elements, the computation times totally become so numerous that the processing time becomes extremely long with a usual processor.
Of course it is possible to shorten the computation time by storing values of sin.theta. and cos.theta. used in the above described formula 1 in a ROM or others (e.g., Hanahara et al., A realtime Processor for Hough Transform, 1985 National Conference of Information System Group, The Institute of Electronics Information and Communication engineers No. 92 or Onda et al. A Hardware Implementation of Hough Transform with ROM, The 70th Anniversary General National Conference of the Institute of Electronics Information and Communication Engineers, No. 1587). But in Hanahara et al., in which the data of the trigonometric calculation are stored in a ROM, the multiplication times for the Formula 1 is still the same, and taking it into account the computation time is considerably longer compared with the addition time, this method cannot provide a fundamental solution.
Onda et al. will be discussed from a different viewpoint. In this method, the computing units for computing the above described Formula 1 are parallelled so as to speed up the overall signal processing. But this parallelism requires the same number of memory tables (ROMs) so as to obtain x.sub.p .multidot.sin.theta., y.sub.p cos.theta. as the parallelled computing units. Consequently the system in terms of hardware becomes very large sized.
This method is not suitable for LSI. The data may be stored in a RAM in place of a ROM, but this has problems with integration
As described above, it has been almost impossible to control in real time a vehicle running at a high speed based on the picture data and recognize in real time an object to be observed moving at a high speed based on The picture data. The speed up of the signal processing by means of parallelled computing units inevitably results in large sizes of the hardware.
A first object of this invention is to provide a picture processing device which enables not only picture data to be processed at high speed and in real time, but also the hardware to be miniaturized.
A second object of this invention is to provide a picture processing system which is able to perform the picture data processing Hough transform is applied to at high speed and in real time.